package com.company.service;

public class LRUMap<K, V> {
    /**
     * 定义链表节点
     *
     * @param <K>
     * @param <V>
     * @author ranger
     */
    private class Node<K, V> {
        private K key;
        private V value;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public Node() {

        }

    }

    /**
     * 缓存最大值
     */
    private int capacity;

    /**
     * 当前缓存数量
     */
    private int size;

    /**
     * 缓存链表头节点
     */
    private Node<K, V> head;

    /**
     * 缓存链表尾节点
     */
    private Node<K, V> tail;

    /**
     * 定义带参构造函数,构造一个为空的双向链表
     *
     * @param capacity 缓存最大容量
     */
    public LRUMap(int capacity) {
        this.capacity = capacity;
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 无参构造函数，初始化容量为16
     */
    public LRUMap() {
        this(16);
    }

    /**
     * 向双向链表中添加节点
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        addNode(key, value);
    }

    /**
     * 根据key获取缓存中的Value
     *
     * @param key
     * @return
     */
    public V get(K key) {
        Node<K, V> retNode = getNode(key);
        if (retNode != null) {
            // 存在，插入头部
            moveToHead(retNode);
            return retNode.value;
        }
        // 不存在
        return null;
    }

    /**
     * 移动给定的节点到头节点
     *
     * @param node
     */
    public void moveToHead(Node<K, V> node) {
        // 如果待移动节点是最后一个节点
        if (node == tail) {
            Node prev = head;
            while (prev.next != null && prev.next != node) {
                prev = prev.next;
            }
            tail = prev;
            node.next = head;
            head = node;
            prev.next = null;

        } else if (node == head) {   // 如果是头节点
            return;
        } else {
            Node prev = head;
            while (prev.next != null && prev.next != node) {
                prev = prev.next;
            }
            prev.next = node.next;
            node.next = head;
            head = node;
        }
    }

    /**
     * 获取给定key的节点
     *
     * @param key
     * @return
     */
    private Node<K, V> getNode(K key) {
        if (isEmpty()) {
            throw new IllegalArgumentException("list is empty,cannot get node from it");
        }
        Node<K, V> cur = head;
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 添加到头节点
     *
     * @param key
     * @param value
     */
    private void addNode(K key, V value) {
        Node<K, V> node = new Node<>(key, value);
        // 如果容量满了，删除最后一个节点
        if (size == capacity) {
            delTail();
        }
        addHead(node);
    }

    /**
     * 删除最后一个节点
     */
    private void delTail() {
        if (isEmpty()) {
            throw new IllegalArgumentException("list is empty,cannot del from it");
        }
        // 只有一个元素
        if (tail == head) {
            tail = null;
            head = tail;
        } else {
            Node<K, V> prev = head;
            while (prev.next != null && prev.next != tail) {
                prev = prev.next;
            }
            prev.next = null;
            tail = prev;
        }

        size--;
    }

    /**
     * 链表是否为空
     *
     * @return
     */
    private boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加节点到头头部
     *
     * @param node
     */
    private void addHead(Node node) {
        // 如果链表为空
        if (head == null) {
            head = node;
            tail = head;
        } else {
            node.next = head;
            head = node;
        }

        size++;

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<K, V> cur = head;
        while (cur != null) {
            sb.append(cur.key)
                    .append(":")
                    .append(cur.value);
            if (cur.next != null) {
                sb.append("->");
            }
            cur = cur.next;
        }
        return sb.toString();
    }
}